package com.cty.twentyEighthDay;

import com.sun.source.tree.Tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/*
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
*/
public class Q_46 {
    // 先序遍历出每个节点的值 然后创建新的链表挂在原节点的右子节点上 时间复杂度O(n) 空间复杂度O(n)
    // 这个方法比较暴力一些
    List<Integer> values = new ArrayList<>();
    public void flatten(TreeNode root) {
        if (root == null) return;
        rootSort(root);
        root.left = null;
        root.right = null;
        TreeNode cur = root;
        for (int i = 1;i < values.size();i++) {
            TreeNode node = new TreeNode(values.get(i));
            cur.right = node;
            cur = cur.right;
        }
    }

    public void rootSort(TreeNode root) {
        if (root == null) {
            return;
        }
        values.add(root.val);
        if (root.left != null) {
            rootSort(root.left);
        }
        if (root.right != null) {
            rootSort(root.right);
        }
    }

    // 力扣视频题解 用迭代实现前序遍历 时间复杂度O(n) 空间复杂度O(n)
    public void flatten2(TreeNode root) {
        if (root == null) return;
        List<Integer> values = new ArrayList<>();
        Stack<TreeNode> stack = new Stack();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                values.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        TreeNode cur = root;
        root.left = null;
        root.right = null;
        for (int i = 1; i < values.size(); i++) {
            cur.right = new TreeNode(values.get(i));
            cur = cur.right;
        }
    }

    // 力扣官方题解 方法二:前序遍历和展开同步进行
    /*
    * 思路:
    *   用一个栈来按先序遍历的顺序压入栈中
    *   用来记录遍历过的节点 边遍历边边建
    *   立链表 注意:建立的速度和遍历的速
    *   度相等 只是提前将当前链表的左右
    *   子节点记录下来而已
    *   时间复杂度(n) 空间复杂度O(n)
    * */
    public void flatten3(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        TreeNode prev = null;
        while (!stack.isEmpty() || root != null) {
            TreeNode cur = stack.pop();
            if (prev != null) {
                prev.left = null;
                prev.right = cur;
            }
            TreeNode left = cur.left,right = cur.right;
            if (right != null) {
                stack.push(right);
            }
            if (left != null) {
                stack.push(left);
            }
            prev = cur;
        }
    }

    // 力扣官方题解 方法三: 寻找前驱节点
    /*
    * 思路:
    *   将当前节点的右子树挂在 当前节点的左子节点的最右边的一个节点
    *   然后将当前节点的左子节点挂在当前节点的right上 将左子节点置
    *   null 将当前节点 指向右子节点 循环操作即可
    *   时间复杂度O(n) 空间复杂度O(1)
    * */
    public void flatten4(TreeNode root) {
        if(root == null) return;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode predecessor = cur.left;
                // 此时找到了左子树的最右边的节点
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }
                predecessor.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}
